package 二叉树;

/**
 * TODO
 * <p>
 * 1、
 * <p/>
 * User: zhaixiaolong Date:2024/2/27 9:30 ProjectName: algorithm Version:
 */
public class 平衡二叉树 {


    public static void main(String[] args) {

    }

    /**
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
     *
     * @param treeNode
     * @return
     */
    public static boolean isBalanceTree(TreeNode treeNode) {
        if (treeNode == null) {
            return true;
        }
        int leftDeep = getDeep(treeNode.getLeft());
        int rightDeep = getDeep(treeNode.getRight());

        boolean rootIsBalance = Math.abs(leftDeep - rightDeep) > 1;
        boolean leftIsBalance = isBalanceTree(treeNode.getLeft());
        boolean rightIsBalance = isBalanceTree(treeNode.getLeft());
        return rootIsBalance && leftIsBalance && rightIsBalance;
    }

    public static int getDeep(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        int leftDeep = getDeep(treeNode.getLeft());
        int rightDeep = getDeep(treeNode.getRight());

        return Math.max(leftDeep, rightDeep) + 1;
    }
}
